package _05_回溯;
/*
    ◼ 回溯可以理解为：通过选择不同的岔路口来通往目的地（找到想要的结果）
    每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试
    ◼ 树、图的深度优先搜索（DFS）、八皇后、走迷宫都是典型的回溯应用

    经典的8皇后问题
 */
public class Main {
    public static void main(String[] args) {
        new Main().placeQueens(4); //摆放8个皇后
    }


    //数组索引是行号，数组的元素是列号,类似于cols[4] = 5,第四行的皇后在第五列
    int[] cols;
    int ways; //一共有多少种摆法

    /**
     * 摆放n个皇后
     * 回溯加剪枝
     * @param n
     */
     void placeQueens(int n){
        if(n<1) return;
        cols = new int[n];
        place(0);
        System.out.println(n+"皇后一共有"+ways+"种摆法");
    }

    /**
     * 从第 row 行 开始摆放皇后
     * @param row
     */

    void place(int row){
        if(row == cols.length){ //base case,n皇后
            ways++;
            show();
            return;
        }
        //总共有八列八行
        // 每一列，每一行都要回溯，但是可以剪枝
        for (int col = 0; col < cols.length; col++) {
            if(isValid(row,col)){ //可以摆放皇后
                //在第row行，第col列摆放皇后
                cols[row] = col;
                //当前行摆放好了以后，摆放下一行
                place(row+1);
                //来到这里，就是回溯
            }
            //剪枝操作，不能摆放，什么也不做，跳过
        }
    }

    /**
     * 判断第 row 行 和 第 col 列 是否可以摆放皇后
     * 当前行，当前列，斜对角线；当前行不用判断，是新的一行
     * 是否可以剪枝
     * @param row
     * @param col
     * @return
     */
    boolean isValid(int row,int col){
        //第row行前面那些行的行号
        for (int i = 0; i < row; i++) {
            //第col列已经有皇后
            if(cols[i] == col){
                System.out.println("["+row+"]["+col+"]=false");
                return false;
            }
            //斜对角线，斜率的知识:同一个坐标轴上 x2-x1/y2-y1 == 1 | -1,表面处在同一个斜线上；斜率相等表明在同一斜线
            //(row - i / col - cols[i] == 1 或者 -1）,代表在同一斜线
            if(row - i == Math.abs(col-cols[i])){
                System.out.println("["+row+"]["+col+"]=false");
                return false;
            }
        }
        System.out.println("["+row+"]["+col+"]=true");
        return true;
    }

    void show(){
        //外部遍历行
        for (int row = 0; row < cols.length; row++) {
            //内部遍历每一行的n列
            for (int col = 0; col < cols.length; col++) {
                if(cols[row] == col){
                    System.out.print("1 ");
                }else{
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("------------------");
    }
}
